package com.example.tree.dp;

import com.example.tree.TreeNode;

/**
 * 给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。
 *  返回包含原始树中所有 最深节点 的 最小子树。
 *  如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。
 *  一个节点的 子树 是该节点加上它的所有后代的集合。
 *
 *  示例 1：
 * 输入：root = [3,5,1,6,2,0,8,null,null,7,4]
 * 输出：[2,7,4]
 * 解释：
 * 我们返回值为 2 的节点，在图中用黄色标记。
 * 在图中用蓝色标记的是树的最深的节点。
 * 注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。
 *
 *  示例 2：
 * 输入：root = [1]
 * 输出：[1]
 * 解释：根节点是树中最深的节点。
 *
 *  示例 3：
 * 输入：root = [0,1,3,null,2]
 * 输出：[2]
 * 解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。
 */
public class Leetcode865_SubtreeWithAllDeepest {
    static class Solution {
        /**
         * 如果当前节点是最深叶子节点的最近公共祖先，那么它的左右子树的高度一定是相等的，
         * 否则高度低的那个子树的叶子节点深度一定比另一个子树的叶子节点的深度小，因此不满足条件。
         * 所以只需要dfs遍历找到左右子树高度相等的根节点即出答案。
         * @param root
         * @return
         */
        public TreeNode subtreeWithAllDeepest(TreeNode root) {
            class Stub {
                TreeNode dfs(TreeNode node) {
                    if (node == null) return null;
                    int leftDepth = getDepth(node.left); // 求左右子节点的深度
                    int rightDepth = getDepth(node.right);
                    if (leftDepth == rightDepth) return node; // 左右子树的高度相等，说明当前节点是最深叶子节点的最近公共祖先
                    else if (leftDepth > rightDepth) return dfs(node.left);
                    else return dfs(node.right);
                }

                private int getDepth(TreeNode node) {
                    return node != null ? Math.max(getDepth(node.left), getDepth(node.right)) + 1 : 0;
                }
            }
            Stub stub = new Stub();
            System.out.println(stub.getDepth(root.left));
            System.out.println(stub.dfs(root).val);
            return stub.dfs(root);
        }
    }

    public static void main(String[] args) {
        //              3
        //     5                   1
        // 6        2         0         8
        //       7     4
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5); root.right = new TreeNode(1);
        root.left.left = new TreeNode(6); root.left.right = new TreeNode(2); root.right.left = new TreeNode(0); root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7); root.left.right.right = new TreeNode(4);
        TreeNode res = new Solution().subtreeWithAllDeepest(root);
        System.out.println(res.val);
    }
}
